package xyz.robinbingo.leetcode.a20.b05.c25;

import java.util.HashMap;
import java.util.Map;

public class LRUCache {

    private int capacity;
    private Map<Integer, CustomNode> map;
    private CustomNode head;
    private CustomNode tail;

    private static class CustomNode {
        private int key;
        private int val;
        private CustomNode pre;
        private CustomNode next;

        public CustomNode(int key, int value) {
            this.key = key;
            this.val = value;
        }

        public CustomNode() {

        }
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        head = new CustomNode();
        tail = new CustomNode();
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        } else {
            CustomNode node = map.get(key);
            move2Head(node);
            return node.val;
        }
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            CustomNode node = map.get(key);
            node.val = value;
            move2Head(node);
        } else {
            if (map.size() == capacity) {
                removeTail();
            }
            CustomNode node = new CustomNode(key, value);
            add2Head(node);
            map.put(key, node);
        }
    }

    private void move2Head(CustomNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
        add2Head(node);
    }

    private void add2Head(CustomNode node) {
        CustomNode old = head.next;
        head.next = node;
        node.pre = head;
        node.next = old;
        old.pre = node;
    }

    private void removeTail() {
        CustomNode old = tail.pre;
        CustomNode node = old.pre;
        node.next = tail;
        tail.pre = node;
        map.remove(old.key);
    }
}